package com.xixi.dataStructure.heap;

/**
 * @Description: Heap
 * @Author: VincentMLiu
 * @Date: 2021-12-16
 * @Version:v1.0
 */
public class Heap {

    private int[] a; // 数组，从下标1开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        if (count >= n) return; // 堆满了
        ++count;
        a[count] = data;
        int i = count;
        while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
            swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
            i = i/2;
        }
    }


    public  void removeMax(){
        if (count == 0) return ; //空堆
        a[1] = a[count]; //堆尾挪到顶端
        --count;
        heapify(a, count, 1);

    }
    /*
     * @Desc: 自上而下堆化
     * @Author vincentML
     * @Date: 2021/12/23 20:06
     * @param a 堆数组
     * @param n 数组当前存储的数据量
     * @param i  堆顶的位置
    */
    private void heapify(int[] a, int n, int i){
        while(true){
            int maxPos = i;
            if(i * 2 <= n && a[i] < a[i *2]) maxPos = i*2; //先判断，如果小于左子树，就把左子树准备上移
            if(i * 2 + 1 <=n && a[maxPos] < a[i*2 + 1]) maxPos = i*2 + 1; //如果右子树比堆顶或者左子树大，就准备上移右子树
            if(maxPos == i) break; //如果i已经比左右子树都打了，说明符合堆化了
            swap(a, i, maxPos); //交换左右子树较大的那一个，上移
            i = maxPos;


        }
    }

    public void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

}
